package com.lry.basic.algorithm.common;

import java.util.*;

/**
 * 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
 *
 * 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
 * 你允许：
 *     装满任意一个水壶
 *     清空任意一个水壶
 *     从一个水壶向另外一个水壶倒水，直到装满或者倒空
 */
public class WaterPuzz {
    public static void main(String[] args) {
//        System.out.println(canMeasureWater(3,5,4));
        System.out.println(canMeasureWater(23,46,12));
    }
    //bfs解法
    public static boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z)
            return false;
        if (x == 0 || y == 0)
            return z == 0 || x + y == z;

        Queue<Node> queue = new LinkedList<>();
        Node node = new Node(0,0);
        queue.offer(node);
        Set<Node> set = new HashSet<>();
        set.add(node);

        while(!queue.isEmpty()){
            Node cur = queue.poll();
            List<Node> list = next(cur.x,cur.y,x,y);
            for(Node tNode:list){
                if(!set.contains(tNode)){
                    queue.offer(tNode);
                    set.add(tNode);
                    if(tNode.x==z||tNode.y==z||tNode.x+tNode.y==z){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    //1 2 1 2
    private static List<Node> next(int a, int b, int x, int y) {
        List<Node> nextList = new ArrayList<>();
        //给a装满水
        nextList.add(new Node(x,b));
        //给b装满水
        nextList.add(new Node(a,y));
        //a倒掉全部水
        nextList.add(new Node(0,b));
        //b倒掉全部水
        nextList.add(new Node(a,0));
        //a倒入b a的水和b剩余容量比较
        int m1 = Math.min(a,y-b);
        nextList.add(new Node(a-m1,b+m1));
        //b倒入a  b的水和a剩余容量比较
        int m2 = Math.min(b,x-a);
        nextList.add(new Node(a+m2,b-m2));
        return nextList;
    }

    //贝祖定理
    public static boolean beizu(int x,int y,int z){
        if (x + y < z)
            return false;
        if (x == 0 || y == 0)
            return z == 0 || x + y == z;
        return z%gcd(x,y)==0;
    }
    //最大公约数
    private static int gcd(int x,int y){
        int r = x%y;
        while(r!=0){
            x = y;
            y = r;
            r = x%y;
        }
        return y;
    }


    static class Node{
        int x;
        int y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            Node node = (Node) obj;
            return this.x==node.x&&this.y==node.y;
        }

        @Override
        public int hashCode() {
            return (""+x+"-"+y).hashCode();
        }
    }

}
